COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00020 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a119.tex[106,phy] \today\hfill}
\font\rmn=cmr9

\bigskip
Let {\bf Z} be the domain of integers, ${\bf Z}↓1=2{\bf Z}+1$ the odd integers,
${\bf Z}↓0=2{\bf Z}$ the even integers, $i=\sqrt{-1}$, 
${\bf G}={\bf Z}+i{\bf Z}$ the Gaussian integers, (complex numbers with
integer components), ${\bf G}↓0=(i+1){\bf G}$ the even Gaussian integers,
${\bf G}↓1={\bf G}↓0+1$ the odd Gaussian integers.
That is, $x+iy$ is even or odd according as $x+y$ is even or odd. As in
the ordinary integers, ${\rm even}+{\rm even}={\rm odd}+{\rm odd}={\rm even}$,
${\rm even}+{\rm odd}={\rm odd}$, ${\rm even}\times{\rm any}={\rm even}$,
${\rm odd}\times {\rm odd}={\rm odd}$.

To enumerate the members of ${\bf G}↓0$ or~${\bf G}↓1$ for which the real
and imaginary parts lie in a specified range, these relations are helpful:
$$\eqalign{{\bf G}↓0&=2{\bf G}+\{0,i+1\}\cr
{\bf G}↓1&=2{\bf G}+\{1,i\}\,.\cr}$$

Let $m=1+i$, so $m↑2=2i$, $m↑4=-4$, $m↑8=16$. Let $W↓0=\{\,w\mid w↑4=1\,\}
=\{\pm 1,\pm i\}$; $iW↓0=W↓0$. Let $W↓j=m↑jW↓0=\{\,w\mid w↑4=(-4)↑j\,\}$;
then $W↓1=\{\pm 1\pm i\}$, $W↓2=2W↓0$, $W↓j=\pm iW↓j=\pm W↓j$,
$W↓{2k}=2↑kW↓0$, $W↓{2k+1}=2↑kW↓1$.

\figbox 1.5in:

\centerline{$W↓0$\quad\qquad\qquad $W↓1$
\qquad\qquad\qquad $W↓2$
\qquad\qquad\qquad\qquad\qquad $W↓3$}

\bigskip
\noindent
Every nonzero Gaussian integer can be factored in a unique way as~$m↑j\zeta$,
where $\zeta\in{\bf G}↓1$. (In fact, $j$~is the largest integer such that
$2↑j$ divides $x↑2+y↑2$.) Define $S↓j=m↑j{\bf G}↓1$; this partitions the
non-zero Gaussian integers into disjoint subsets.

This diagram shows for each $x+iy$ the $j$ such that $x+iy\in S↓j$.

$$\vcenter{\offinterlineskip%
\halign{$\hfil#\hfil$
&$\hfil#\hfil$\enspace
&\vrule#
&\strut\quad$\hfil#\hfil$\quad
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\hfil\quad$
&$\hfil#\quad$\cr
&y\cr
x&&\omit&0&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\smallskip}
\noalign{\hrule}
&&height2pt\cr
&0&&&0&2&0&4&0&2&0&6&0&2\cr
&1&&0&1&0&1&0&1&0&1&0&1&0\cr
&2&&2&0&3&0&2&0&3&0&2&0&3\cr
&3&&0&1&0&1&0&1&0&1&0&1&0\cr
&4&&4&0&2&0&5&0&2&0&4&0&2\cr
&5&&0&1&0&1&0&1&0&1&0&1&0\cr
&6&&2&0&3&0&2&0&3&0&2&0&3\cr
&7&&0&1&0&1&0&1&0&1&0&1&0\cr
&8&&6&0&2&0&4&0&2&0&7&0&2\cr
&9&&0&1&0&1&0&1&0&1&0&1&0\cr
&10&&2&0&3&0&2&0&3&0&2&0&3\cr}}$$

\vfill\eject

To iterate through the members of $S↓j$, separate the cases $j$~even
and $j$~odd:
$$\eqalign{S↓{2k}&=(2i)↑k{\bf G}↓1=2↑k{\bf G}↓1=2↑k(2{\bf G}+\{1,i\})\cr
&=(2↑{k+1}{\bf G}+2↑k)\cup (2↑{k+1}{\bf G}+i2↑k)\cr
&=\bigl((2↑{k+1}{\bf Z}+2↑k)+i2↑{k+1}{\bf Z}\bigr)\cup
\bigl(2↑{k+1}{\bf Z}+i(2↑{k+1}{\bf Z}+2↑k)\bigr)\,,\cr
S↓{2k+1}&=2↑kS↓1=2↑k(2{\bf G}+1+i)=(2↑{k+1}{\bf Z}+2↑k)+i(2↑{k+1}{\bf Z}+2↑k)
\,.\cr}$$
Iterations over the members of $S↓j$ in
regions bounded in their real and imaginary parts are readily expressed
by replacing each occurrence of~{\bf Z} above by a finite interval of~{\bf Z}.

To generate all values $x+iy$ in $S↓{2k}$ for which $a<x≤b$ and $c<y≤d$,
first iterate over integers~$p$ and~$q$ for which
$$\eqalign{a<2↑{k+1}p+2↑k≤b&\quad\hbox{and}\quad c<2↑{k+1}q≤d\,,\cr
\noalign{\smallskip}
{a-2↑k\over 2↑{k+1}}<p≤{b-2↑k\over 2↑{k+1}}
&\quad\hbox{and}\quad 
{c\over 2↑{k+1}}<q≤{d\over 2↑{k+1}}\,,\cr
\noalign{\smallskip}
\left\lfloor{a-2↑k\over 2↑{k+1}}\right\rfloor<p≤
\left\lfloor{b-2↑k\over 2↑{k+1}}\right\rfloor
&\quad\hbox{and}\quad 
\left\lfloor{c\over 2↑{k+1}}\right\rfloor
<q≤\left\lfloor{d\over 2↑{k+1}}\right\rfloor\,,\cr
\noalign{\smallskip}
\left\lfloor{a+2↑k\over 2↑{k+1}}\right\rfloor≤p≤
\left\lfloor{b-2↑k\over 2↑{k+1}}\right\rfloor
&\quad\hbox{and}\quad 
\left\lfloor{c+2↑{k+1}\over 2↑{k+1}}\right\rfloor
≤q≤\left\lfloor{d\over 2↑{k+1}}\right\rfloor\,.\cr}$$
For each $p$, $x=2↑{k+1}p+2↑k$, and for each~$q$, $y=2↑{k+1}q$. Then
similarly iterate over
$$\left\lfloor{a+2↑k\over 2↑{k+1}}\right\rfloor≤p≤
\left\lfloor{b\over 2↑{k+1}}\right\rfloor
\quad\hbox{and}\quad 
\left\lfloor{c+2↑k\over 2↑{k+1}}\right\rfloor
≤q≤\left\lfloor{d-2↑k\over 2↑{k+1}}\right\rfloor\,,$$
with $x=2↑{k+1}p$ and $y=2↑{k+1}q+2↑k$.

To generate all values of $x+iy$ in $S↓{2k+1}$ for which $a<x≤b$ and 
$c<y≤d$, iterate over~$p$ and~$q$ for which
$$\left\lfloor{a+2k\over 2↑{k+1}}\right\rfloor≤p≤
\left\lfloor{b-2↑k\over 2↑{k+1}}\right\rfloor
\quad\hbox{and}\quad 
\left\lfloor{c+2↑k\over 2↑{k+1}}\right\rfloor
≤q≤\left\lfloor{d-2↑k\over 2↑{k+1}}\right\rfloor\,,$$
with $x=2↑{k+1}p+2↑k$, $y=2↑{k+1}q+2↑k$.

Suppose we have an infinite digitized image {\tt DARK[{\bf G}]};
initially {\tt DARK[$z$]} is 1.0 if $z$ is the location of a black
pixel, $-1.0$ if $z$ is a white pixel, and may have intermediate values.
We want to generate a corresponding bit matrix, $B[G]$, in which the bits
are represented by $+1$ (black) and $-1$ (white), such that $B$ and~$D$,
when printed and filtered, are similar. Here is a proposed algorithm:

\vfill\eject

\smallskip\halign{\tt #\hfil\cr
FOR J:=0 TO infinity DO\cr
\quad BEGIN\cr
\quad FOR $z\in S↓j$ DO\cr
\qquad BEGIN\cr
\qquad TEMP[$z$]:=4*DARK[$z$];\cr
\qquad FOR $w\in W↓j$ DO\cr
\qquad\quad TEMP[$z$]:=TEMP[$z$] $+$ DARK[$z+w$];\cr
\qquad $B$[$z$]:=sign(TEMP[$z$]);\cr
\qquad ERROR[$z$]:=(DARK[$z$] $-\;B$[$z$])/4;\cr
\qquad FOR $w\in W↓j$ DO\cr
\qquad\quad DARK[$z+w$]:=DARK[$z+w$] $+$ ERROR[$z$]\cr
\qquad END\cr
\quad END\cr}

\smallskip\noindent
The only reason {\tt ERROR} and {\tt TEMP} are subscripted is to allow
the $z$-iteration to be done in parallel. The $w$-iteration may also be
done in parallel.

Next we include the gory details of generating~$S↓j$ and~$W↓j$, while
restricting $z$ and $z+w$ to the {\tt PICTURE} region $(1:b)+i(1:d)$.
Outside the picture region, {\tt DARK[$z$]} is treated as a constant
zero; this is the reason for letting the gray scale run from~$-1$ to~$+1$.
We also partially unwind the $j$~iteration, letting $k$ run from zero to
infinity, with $j$ equal first to~$2k$, then to $2k+1$. Invariants include
$r=2↑k$, $t=2↑{k+1}$.

\smallskip\halign{\tt #\hfil\cr
$\{$Initialize$\}$\cr
$k:=0$; $r:=1$; $t:=2$;\cr
WHILE ($r≤b$) AND ($r≤d$) DO $\{k=0,1,2,\ldots\}$\cr
$\{j=2k$; $W↓j=$ set($\langle r,0\rangle$,$\langle -r,0\rangle$,%
$\langle 0,r\rangle$,$\langle 0,-r\rangle$); $S=r${\bf G}$↓1\}$\cr
\quad BEGIN\cr
\quad $u[1]:=r$; $v[1]:=0$; $u[2]:=-r$; $v[2]:=0$;\cr
\quad $u[3]:=0$; $v[3]:=r$; $u[4]:=0$; $v[4]:=-r$;\cr
\quad FOR $p:=0$ TO ($b-r$) DIV $t$ DO\cr
\quad\quad BEGIN\cr
\quad\quad $x:=t*p+r$; $\{0<x≤b\}$\cr
\quad\quad FOR $q:=1$ TO $d$ DIV $t$ DO\cr
\quad\quad\quad BEGIN\cr
\quad\quad\quad $y:=t*q$; $\{0<y≤d\}$\cr
\quad\quad\quad $\{x\in t{\bf Z}+r,y\in t{\bf Z}\}$\cr
\quad\quad\quad $\{$macro$\}$\cr
\quad\quad\quad TEMP $:= 4.0\;*$ DARK$[x,y]$;\cr
\quad\quad\quad FOR $n:=1$ TO $4$ DO\cr
\quad\quad\quad\quad IF OK THEN\cr
\quad\quad\quad\quad\quad TEMP $:=$ TEMP $+$ DARK$\bigl[x+u[n],y+v[n]\bigr]$;\cr
\quad\quad\quad $\{$OK stands for $0<x+u[n]≤b$, $0≤y+v[n]≤d\}$\cr
\quad\quad\quad IF TEMP $≥$ 0 THEN $B[x,y]:=1$ ELSE $B[x,y]:=-1$;\cr
\quad\quad\quad ERROR $:=$ $($DARK$[x,y]+B[x,y]) * 0.25$;\cr
\quad\quad\quad FOR $n:=1$ TO $4$ DO\cr
\quad\quad\quad\quad IF OK THEN\cr
\quad\quad\quad\quad\quad DARK$\bigl[x+u[n],y+v[n]\bigr]\,:=$ 
DARK$\bigl[x+u[n],y+v[n]\bigr]+{\tt ERROR}$\cr
\quad\quad\quad $\{$end macro$\}$\cr
\quad\quad\quad END $\{y\}$\cr
\quad\quad END $\{x\}$;\cr
%}
%\vfill\eject
%\smallskip\halign{\tt #\hfil\cr
\quad FOR $p:=1$ TO $b$ DIV $t$ DO\cr
\quad\quad BEGIN\cr
\quad\quad $x:=t*p$;\cr
\quad\quad FOR $q:=0$ TO ($d-r$) DIV $t$ DO\cr
\quad\quad\quad BEGIN\cr
\quad\quad\quad $y:=t*q+r$; $\{x\in t{\bf Z},y\in t{\bf Z}+r\}$\cr
\quad\quad\quad $\{$copy above macro here$\}$\cr
\quad\quad\quad END $\{y\}$\cr
\quad\quad END $\{x\}$;\cr
\quad $\{j=2k+1$; $W↓j=$ set($\langle r,r\rangle$,$\langle r,-r\rangle$,%
$\langle -r,r\rangle$,$\langle -r,-r\rangle$);\cr
\quad $S↓j=r({\bf Z}↓1+i{\bf Z}↓1)=(t{\bf Z}+r)+i(t{\bf Z}+r)\}$\cr
\quad $v[1]:=r$; $v[2]:=-r$; $u[3]:=-r$; $u[4]:=r$;\cr
\quad FOR $p:=0$ TO ($b-r$) DIV $t$ DO\cr
\quad\quad BEGIN\cr
\quad\quad $x:=t*p+r$;\cr
\quad\quad FOR $q:=0$ TO ($d-r$) DIV $t$ DO\cr
\quad\quad\quad BEGIN\cr
\quad\quad\quad $y:=t*q+r$;\cr
\quad\quad\quad $\{$copy above macro here$\}$\cr
\quad\quad\quad END $\{y\}$;\cr
\quad\quad END $\{x\}$;\cr
\quad $\{$prepare for next value of $k\}$\cr
\quad $k:=k+1$; $r:=t$; $t:=2*t$\cr
\quad END $\{k\}$\cr
}

\smallskip
For maximum efficiency of parallel execution, the algorithm should be
implemented in this way:

\smallskip
\display 30pt:(1):
Copy the macro as specified.

\smallskip
\display 30pt:(2):
Unwind each of the three $n$-loops.

\smallskip
\display 30pt:(3):
Subscript {\tt TEMP} and {\tt ERROR} so that the statements

\smallskip
\halign{\qquad\qquad\qquad\tt #\hfil\cr
TEMP$[x,y] := 4.0 * {\tt DARK}[x,y]$,\cr
TEMP$[x,y] := {\tt TEMP}[x,y] + {\tt DARK}\bigl[x+u[n],y+v[n]\bigr]$,\cr
IF TEMP$[x,y] ≥0$ THEN $B[x,y] :=1$ ELSE $B[x,y] :=-1$,\cr
ERROR$[x,y] := ($DARK$[x,y]-B[x,y]) *0.25$;\cr
DARK$\bigl[x+u[n],y+v[n]\bigr]:= {\tt DARK}\bigl[x+u[n],y+v[n]\bigr]+{\tt ERROR}%
[x,n]$\cr}
 
\smallskip
\display 30pt::
can each be done in parallel.

\smallskip
\display 30pt:(4):
Control each of the statements with its own $p$- and $q$-iterations,
incorporating conditions like $x+u[n]≤b$ into the  iteration bounds.












\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd

First draft May 26, 1987. 
%revised: May 6, 1987.
%subsequently revised.

\bye